Collaborative Web Hosting by Reaz Ahmed & Raouf Boutaba

Author:Reaz Ahmed & Raouf Boutaba
Language: eng
Format: epub
Publisher: Springer International Publishing, Cham

4.2.1.2 Non-structured Techniques

Unstructured systems ([1, 2]) identify objects by keywords. Advertisements and queries are expressed in terms of the keywords associated with the shared objects. Structured systems, on the other hand, identify objects by keys, generated by applying one-way hash function on keywords associated with an object. Key-based query routing is much efficient than keyword-based unstructured query routing. The downside of key-based query routing is the lack of support for partial-matching semantics as discussed in the previous section. Unstructured systems, utilizing blind search methods such as Flooding [1] and Random-walk [16], can easily be modified to support partial-matching queries. But, due to the lack of proper routing information, the generated query routing traffic would be very high. Besides, there would be no guarantee on search completeness.

Many research activities are aimed at improving the routing performance of unstructured P2P systems. Different routing hints are used in different approaches. In [3], routing is biased by peer capacity; queries are routed to peers of higher capacity with higher probability. In [29] and [33], peers learn from the results of previous routing decisions and bias future query routing based on this knowledge. In [4], peers are organized based on common interest, and restricted flooding is performed in different interest groups. Many research works ([3, 13, 33], etc.) propose storing index information from peers within a radius of 2 or 3 hops on the overlay network. All of these techniques reduce the volume of search traffic to some extent, but none provides guarantee on search completeness.

Bloom filters are used by a few unstructured P2P systems for improving query routing performance. In [13] each peer stores Bloom filters from peers one or two hops away. Three ways of aggregating Bloom-filters are also presented. Experimental results presented in [13] show that logical OR-based aggregation of Bloom filters is not suitable for indexing information from peers more than one hop away. In [21] each peer stores a list of Bloom filters per neighbor. The ith Bloom filter in the list of Bloom filters for neighbor M summarizes the resources that are i − 1 hops away from neighbor M. A query is forwarded to the neighbor with a matching Bloom filter at the smallest hop-distance. This approach aims at finding the closest replica of a document with a high probability.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.